﻿#pragma warning(disable:4996)
#pragma warning(disable:6031)
#pragma warning(disable:6011)
/*
06-图1 列出连通集 (25 分)
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:
按照"{v​1 v2 ... vk}"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }*/

namespace Y190711_exam06_1 {
int main();

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

#define MaxVertexNum 11			/* 最大顶点数 */
typedef int Vertex;				/* 用顶点下标表示顶点,为整型 */
typedef int WeightType;			/* 边的权值设为整型 */
typedef char DataType;			/* 顶点存储的数据类型设为字符型 */

/* 边的定义 */
typedef struct ENode {
	Vertex v1, v2;		/* 有向边<V1, V2> */
	WeightType weight;	/* 权重 */
}ENode, *PtrToENode, *Edge;

/* 邻接点的定义 */
typedef struct AdjVNode* PtrToAdjVNode;
typedef struct AdjVNode {
	Vertex adjV;			/* 邻接点下标 */
	WeightType weight;		/* 边权重 */
	PtrToAdjVNode next;		/* 指向下一个邻接点的指针 */
}AdjVNode;

/* 顶点表头结点的定义 */
typedef struct VNode{
	PtrToAdjVNode firstEdge;	/* 边表头指针 */
	DataType data;				/* 存顶点的数据 */
	/* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];

/* 图结点的定义 */
typedef struct GNode* PtrToGNode;
struct GNode {
	int nv;		/* 顶点数 */
	int ne;     /* 边数   */
	AdjList g;	/* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

LGraph CreateGraph(int vertexNum) {
	Vertex v;
	LGraph graph;

	graph = (LGraph)malloc(sizeof(struct GNode)); /*建立图*/
	graph->nv = vertexNum;
	graph->ne = 0;
	/* 初始化邻接表头指针 */
	/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
	for (v = 0; v < graph->nv; v++)
		graph->g[v].firstEdge = NULL;
	return graph;
}

void insertEdge(LGraph graph, Edge e) {
	PtrToAdjVNode newNode;

	/* 插入边 <V1, V2> */
	/* 为V2建立新的邻接点 */
	newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	newNode->adjV = e->v2;
	newNode->weight = e->weight;
	/* 将V2插入V1的表头 */
	newNode->next = graph->g[e->v1].firstEdge;
	graph->g[e->v1].firstEdge = newNode;

	/* 若是无向图，还要插入边 <V2, V1> */
	/* 为V1建立新的邻接点 */
	newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	newNode->adjV = e->v1;
	newNode->weight = e->weight;
	/* 将V1插入V2的表头 */
	newNode->next = graph->g[e->v2].firstEdge;
	graph->g[e->v2].firstEdge = newNode;
}

LGraph buildGraph() {
	LGraph graph;
	Edge e;
	//Vertex v;
	int nv, i;
	freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/DataStructure/test_data/zju_e06_01.txt", "r", stdin);
	scanf("%d", &nv);
	graph = CreateGraph(nv);
	scanf("%d", &(graph->ne));   /* 读入边数 */
	if (graph->ne > 0) {
		e = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
		/* 读入边，格式为"起点 终点"，插入邻接矩阵 */
		for (i = 0; i < graph->ne; i++) {
			e->weight = 0;
			scanf("%d %d", &e->v1, &e->v2); //,&E->Weight); 
			/* 注意：如果权重不是整型，Weight的读入格式要改 */
			insertEdge(graph, e);
		}
	}
	/* 如果顶点有数据的话，读入数据 */
	/*
	for (v = 0; v < graph->nv; v++)
		scanf(" %c", &(graph->g[v].data));
	//*/
	return graph;
}

int Visited[MaxVertexNum] = {};
int Visited_cache[MaxVertexNum] = {};
int cache_index = 0;

void reset_visited() {
	for (int i = 0; i < MaxVertexNum; i++)
		Visited[i] = 0;
}

void reset_visited_cache() {
	for (int i = 0; i < MaxVertexNum; i++)
		Visited_cache[i] = 0;
	cache_index = 0;
}

void Visit(Vertex v)
{
	Visited_cache[cache_index++] = v;
}

void DFS(LGraph graph, Vertex v, void (*Visit)(Vertex)) 
{
	PtrToAdjVNode w;
	Visit(v);
	Visited[v] = 1;
	for (w = graph->g[v].firstEdge; w; w = w->next) {
		if (!Visited[w->adjV])
			DFS(graph, w->adjV, Visit);
	}
}

int main()
{
	LGraph graph;
	graph = buildGraph();
	for (int i = 0; i < graph->nv; i++) {
		reset_visited_cache();
		if (!Visited[i]) {
			DFS(graph, i, Visit);
			printf("{ ");
			for (int j = 0; j < cache_index; j++) {
				printf("%d ", Visited_cache[j]);
			}
			printf("}\n");
		}
	}
	return 0;
}

}

int main_Y190711_exam06_1()
{
	return Y190711_exam06_1::main();
}